package com.tarry.sort;

import java.util.Arrays;

/**
 * 插入排序
 * <br>
 * (1) 插入排序是原地排序算法
 * <br>
 * (2) 插入排序是稳定排序算法
 * <br>
 * result=>j+1 :0      <br>
 * 第1次排序结果。    <br>
 * 3 7 5 6 4 2     <br>
 * result=>j+1 :1      <br>
 * 第2次排序结果。    <br>
 * 3 7 5 6 4 2     <br>
 * 交换数据结果：     <br>
 * 3 7 7 6 4 2     <br>
 * result=>j+1 :1      <br>
 * 第3次排序结果。    <br>
 * 3 5 7 6 4 2     <br>
 * 交换数据结果：     <br>
 * 3 5 7 7 4 2  <br>
 * result=>j+1 :2 <br>
 * 第4次排序结果。 <br>
 * 3 5 6 7 4 2 <br>
 * 交换数据结果： <br>
 * 3 5 6 7 7 2 <br>
 * 交换数据结果： <br>
 * 3 5 6 6 7 2 <br>
 * 交换数据结果： <br>
 * 3 5 5 6 7 2 <br>
 * result=>j+1 :1 <br>
 * 第5次排序结果。 <br>
 * 3 4 5 6 7 2 <br>
 * 交换数据结果： <br>
 * 3 4 5 6 7 7 <br>
 * 交换数据结果： <br>
 * 3 4 5 6 6 7 <br>
 * 交换数据结果： <br>
 * 3 4 5 5 6 7 <br>
 * 交换数据结果： <br>
 * 3 4 4 5 6 7 <br>
 * 交换数据结果： <br>
 * 3 3 4 5 6 7 <br>
 * result=>j+1 :0 <br>
 * 第6次排序结果。 <br>
 * 2 3 4 5 6 7 <br>
 * 排序结果 <br>
 * 2 3 4 5 6 7 <br>
 */
public class InsertSort {

    public static void main(String[] args) {
        int[] arrays = new int[]{3,7,5,6,4,2};
        InsertSort.sort(arrays);
        System.out.print("排序结果\n");
        System.out.println(Arrays.toString(arrays));
    }

    public static void sort(int[] arrays){
        if (arrays.length == 0) {
            throw new RuntimeException("The array is empty !");
        }
        for (int i = 0; i < arrays.length; i++) {
            int tmp = arrays[i];
            // 查找插入位置
            int j = i - 1;
            // 用第i位第数字和第 0～ i-1 个数字进行比较
            for (; j >= 0 ; j--){
                if (arrays[j] > tmp) {
                    // 移动移位
                    arrays[j+1] = arrays[j];
                }else {
                    break;
                }
                System.out.println("交换数据结果：");
                InsertSort.print(arrays);
            }
            // 插入数据，此时 j+1 = i
            System.out.println("result=>j+1 :" + (j + 1));
            arrays[j+1] = tmp;
            System.out.printf("第%d次排序结果。\n",(i + 1));
            InsertSort.print(arrays);
        }
    }

    public static void print(int[] arrays){
        for (int array : arrays) {
            System.out.printf("%d ", array);
        }
        System.out.print("\n");
    }
}
